#
# @lc app=leetcode.cn id=712 lang=python3
#
# [712] 两个字符串的最小ASCII删除和
#

# @lc code=start
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        s1 = " " + s1
        s2 = " " + s2

        m = len(s1)
        n = len(s2)
        dp = [[0 for i in range(n)] for j in range(m)]

        dp[0][0] = 0
        for i in range(1, m, 1):
            dp[i][0] = dp[i-1][0] + ord(s1[i]) 
        for i in range(1, n, 1):
            dp[0][i] = dp[0][i-1] + ord(s2[i]) 
        for i in range(1, m, 1):
            for j in range(1, n, 1):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min((dp[i][j-1] + ord(s2[j])), (dp[i-1][j] + ord(s1[i])))
        
        # print(dp)
        return dp[m-1][n-1]
# @lc code=end

